const basicMap = [] // 迷宫数据
const visited = [] // 逻辑访问数据
const range = [[-1, 0], [0, 1], [1, 0], [0, -1]] // 偏移量
/**
 * 生成地基，每个可通行的方格都间隔一堵墙
 */
function createBasis(x, y) {
  for (let i = 0; i < x; i++) {
    let line = new Array(y).fill(0)
    visited.push(new Array(y).fill(false))
    if (i % 2 === 1) {
      for (let j = 0; j < line.length; j++) {
        if (j % 2 === 1) {
          line[j] = 1
        }
      }
    }
    basicMap.push(line)
  }
}

/**
 * 渲染map
 */
function renderMap() {
  const className = ['wall', 'road']
  let dom = ''
  for (let i = 0; i < basicMap.length; i++) {
    let line = '<div class="line">'
    for (let j = 0; j < basicMap[i].length; j++) {
      line += `<div class="${className[basicMap[i][j]]}"></div>`
    }
    line += '</div>'
    dom += line
  }
  const mapDom = document.getElementById('map')
  mapDom.style.height = 30 * basicMap.length + 'px'
  mapDom.style.width = 30 * basicMap[0].length + 'px'
  mapDom.innerHTML = dom
}

/**
 * 判断是否越界
 * @param x
 * @param y
 * @returns {boolean|boolean}
 */
function isRange(x, y) {
  return x > 0 && x < basicMap.length - 1 && y > 0 && y < basicMap[0].length - 1
}

function* createMaze() {
  let stack = []
  stack.push({x: 1, y: 1})
  visited[1][1] = true
  while (stack.length > 0) {
    let curPos
    if (Math.random() > 0.5){
      curPos = stack.shift()
    } else {
      curPos = stack.pop()
    }
    for (let i = 0; i < 4; i++) {
      let newX = curPos.x + range[i][0] * 2  // 两步是 *2
      let newY = curPos.y + range[i][1] * 2
      // 坐标没有越界 且 没有被访问过
      if (isRange(newX, newY) && !visited[newX][newY]) {
        yield
        basicMap[(newX + curPos.x) / 2][(newY + curPos.y) / 2] = 1
        if (Math.random() > 0.5){
          stack.push({x: newX, y: newY})
        } else {
          stack.unshift({x: newX, y: newY})
        }
        visited[newX][newY] = true
      }
    }
  }
}

// 创建19*19的地图，路的四面都为墙
createBasis(19, 19)
// 设置开始和结束点为左上角和右下角
basicMap[1][0] = 1
basicMap[basicMap[0].length - 2][basicMap.length - 1] = 1

// 渲染地图
renderMap()
// 处理生成迷宫
const createStep = createMaze()
const t = setInterval(() => {
  let n = createStep.next()
  // 渲染地图
  renderMap()
  if (n.done) {
    clearInterval(t)
  }
}, 100)
